< >

Spacious Maximus

TIME LIMIT = 1 SEC.

COVID-19. COVID-19. COVID-19.
It has been one of the most important events of this decade. Massive shutdowns everywhere, all over the world. It has brought the world economy to a standstill. But for hostelers of VBIT, this is good news. They can go to their homes and stay there till March 31st, surrounded by their loved ones.
C.H.R.I.S. is also one of them. He has a bit of a problem though, and he needs your help. To make packing easier, he bought a box (cube) of 100 x 100 x 100 inches³. And all the stuff that he has to pack are cuboid-shaped. Given the size of all his stuff, find the maximum number of items that he can take.

Input	Output
The first line will contain N, the number of items he wants to pack. The next N line will contain three space-separated integers - the dimensions of the item - length, breadth and height.	The maximum number of items he can pack.

Constraints

1 ≤ T ≤ 10⁶
1 ≤ Length, Breadth, Height ≤ 10⁶

Example Test Case

Input	Output
4 2 2 2 3 3 3 4 4 4 100 100 100	3

Solution

#include <iostream> #include <algorithm> #include <set> #include <iterator> using namespace std; int main() { long long int n,i,length,breadth,height,sum=0,c=0; cin>>n; // A multiset is used to have repeated elements in an ascending order. // This is used here because we want to have as many items in the box as possible. multiset<long long int> volumes; multiset<long long int>::iterator it; for(i=0;i<n;i++) { cin>>length>>breadth>>height; volumes.insert(length*breadth*height); } // We add the volumes of as many items as possible (due to their ascending order of volumes), // and break out of the loop when we're either full or cannot add the next item due to insufficient space. // All of this is performed while keeping a count of how many items have been added. for(it = volumes.begin(); it!=volumes.end(); ++it) { if((sum+*it)<=1000000) { sum+=*it; c++; } else break; } cout<<c; return 0; }